package com.lin.benchmade.ternary;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Vector;

import com.lin.benchmade.utils.Hit;

public class TernarySearchTrie {
	/**
	 * 比较char，按照字典（alfabetical）顺序
	 * @param cCompare2 The first char in the comparison.
	 * @param cRef The second char in the comparison.
	 * @return A negative number, 0 or a positive number if the second char is less, equal or greater.
	 */
	private static int compareCharsAlphabetically(char cCompare2, char cRef) {
		return Character.toLowerCase(cCompare2) - Character.toLowerCase(cRef);
	}

	/**默认匹配后返回的结果数
	 * The default number of values returned by the <code>matchAlmost</code>method.
	 */
	private int defaultNumReturnValues = -1;

	/**允许模糊的字符数，最小0，最大3。the number of differences allowed in a call to the matchAlmostKey*/
	private int matchAlmostDiff;

	private TSTNode rootNode;//The base node in the trie.

	public TernarySearchTrie() {
	}//Constructs an empty Ternary Search Trie.

	void setRoot(TSTNode newRoot) {// for loading
		rootNode = newRoot;
	}

	TSTNode getRoot() {// for saving
		return rootNode;
	}

	/**
	 *  构造一个三叉树，从一个文件加载数据到三叉树
	 * into the Trie. The file is a normal text document, where each line is of
	 * the form "word TAB float".
	 * @param file  The <code>File</code> with the data to load into the Trie.
	 * @exception IOException A problem occured while reading the data.
	 */
	public TernarySearchTrie(File file) throws IOException {
		this();
		BufferedReader in = new BufferedReader(new InputStreamReader((new FileInputStream(file))));
		String word;
		int pos;
		Float occur, one = new Float(1);
		while ((word = in.readLine()) != null) {
			pos = word.indexOf("\t");
			occur = one;
			if (pos != -1) {
				occur = Float.parseFloat(word.substring(pos + 1).trim());
				word = word.substring(0, pos);
			}
			String key = word.toLowerCase();
			if (rootNode == null) {
				rootNode = new TSTNode(key.charAt(0), null);
			}
			TSTNode node = null;
			if (key.length() > 0 && rootNode != null) {
				TSTNode currentNode = rootNode;
				int charIndex = 0;
				while (true) {
					if (currentNode == null)
						break;
					//char比较，char的unicode差,  arg0>arg1是正数，否则是负数
					int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
					if (charComp == 0) {//等于0说明相等
						charIndex++;
						if (charIndex == key.length()) {//如果游标走到了String的尽头。赋值并跳出
							node = currentNode;
							break;
						}
						currentNode = currentNode.relatives[TSTNode.EQKID];
					} else if (charComp < 0) {
						currentNode = currentNode.relatives[TSTNode.LOKID];
					} else {
						currentNode = currentNode.relatives[TSTNode.HIKID];
					}
				}
				Float occur2 = null;
				if (node != null)
					occur2 = ((Float) (node.data));
				if (occur2 != null) {
					occur += occur2.floatValue();
				}
				currentNode = getOrCreateNode(word.trim().toLowerCase());
				currentNode.data = occur;
			}
		}
		in.close();
	}

	/**
	 * Retrieve the object indexed by a key.
	 * @param key
	 *            A <code>String</code> index.
	 * @return The object retrieved from the Ternary Search Trie.
	 */
	public Object get(CharSequence key) {
		TSTNode node = getNode(key);
		if (node == null) {
			return null;
		}
		return node.data;
	}

	/**
	 * Retrieve the <code>Float</code> indexed by key, increment it by one unit
	 * and store the new <code>Float</code>.
	 * @param key
	 *            A <code>String</code> index.
	 * @return The <code>Float</code> retrieved from the Ternary Search Trie.
	 */
	public Float getAndIncrement(String key) {
		String key2 = key.trim().toLowerCase();
		TSTNode node = getNode(key2);
		if (node == null) {
			return null;
		}
		Float aux = (Float) (node.data);
		if (aux == null) {
			aux = new Float(1);
		} else {
			aux = new Float(aux.intValue() + 1);
		}
		put(key2, aux);
		return aux;
	}

	/**
	 * Stores a value in the trie. The value may be retrieved using the key.
	 * 
	 * @param key
	 *            A <code>String</code> that indexes the object to be stored.
	 * @param value
	 *            The object to be stored in the Trie.
	 */
	public void put(CharSequence key, Object value) {
		getOrCreateNode(key).data = value;
	}

	/**
	 * Returns the node indexed by key, creating that node if it doesn't exist,
	 * and creating any required intermediate nodes if they don't exist.
	 * 
	 * @param key
	 *            A <code>String</code> that indexes the node that is returned.
	 * @return The node object indexed by key. This object is an instance of an
	 *         inner class named <code>TernarySearchTrie.TSTNode</code>.
	 * @exception NullPointerException
	 *                If the key is <code>null</code>.
	 * @exception IllegalArgumentException
	 *                If the key is an empty <code>String</code>.
	 */
	protected TSTNode getOrCreateNode(CharSequence key) throws NullPointerException, IllegalArgumentException {
		if (key == null) {
			throw new NullPointerException("attempt to get or create node with null key");
		}
		if (key.length() == 0) {
			throw new IllegalArgumentException("attempt to get or create node with key of zero length");
		}
		if (rootNode == null) {
			rootNode = new TSTNode(key.charAt(0), null);
		}
		TSTNode currentNode = rootNode;
		int charIndex = 0;
		while (true) {
			int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return currentNode;
				}
				if (currentNode.relatives[TSTNode.EQKID] == null) {
					currentNode.relatives[TSTNode.EQKID] = new TSTNode(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				if (currentNode.relatives[TSTNode.LOKID] == null) {
					currentNode.relatives[TSTNode.LOKID] = new TSTNode(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				if (currentNode.relatives[TSTNode.HIKID] == null) {
					currentNode.relatives[TSTNode.HIKID] = new TSTNode(key.charAt(charIndex), currentNode);
				}
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	/**
	 * Returns the key that indexes the node argument.
	 * @param node
	 *            The node whose index is to be calculated.
	 * @return The <code>String</code> that indexes the node argument.
	 */
	protected String getKey(TSTNode node) {
		StringBuffer getKeyBuffer = new StringBuffer();
		getKeyBuffer.setLength(0);
		getKeyBuffer.append("" + node.splitchar);
		TSTNode currentNode;
		TSTNode lastNode;
		currentNode = node.relatives[TSTNode.PARENT];
		lastNode = node;
		while (currentNode != null) {
			if (currentNode.relatives[TSTNode.EQKID] == lastNode) {
				getKeyBuffer.append("" + currentNode.splitchar);
			}
			lastNode = currentNode;
			currentNode = currentNode.relatives[TSTNode.PARENT];
		}
		getKeyBuffer.reverse();
		return getKeyBuffer.toString();
	}

	/**
	 * Returns the node indexed by key, or <code>null</code> if that node
	 * doesn't exist. Search begins at root node.
	 * @param key
	 *            A <code>String</code> that indexes the node that is returned.
	 * @return The node object indexed by key. This object is an instance of an
	 *         inner class named <code>TernarySearchTrie.TSTNode</code>.
	 */
	public TSTNode getNode(CharSequence key) {
		return getNode(key, rootNode);
	}

	/**
	 * Returns the node indexed by key, or <code>null</code> if that node
	 * doesn't exist. The search begins at root node.
	 * 
	 * @param key
	 *            A <code>String</code> that indexes the node that is returned.
	 * @param startNode
	 *            The top node defining the subtrie to be searched.
	 * @return The node object indexed by key. This object is an instance of an
	 *         inner class named <code>TernarySearchTrie.TSTNode</code>.
	 */
	private TSTNode getNode(CharSequence key, TSTNode startNode) {
		if (key == null || startNode == null || key.length() == 0) {
			return null;
		}//一些必要条件的检查

		TSTNode currentNode = startNode;
		int charIndex = 0;
		while (true) {
			if (currentNode == null) {
				return null;
			}
			int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return currentNode;
				}
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}
	
	/**
	 * 因为merge的时候,都是验证前缀是否合法,组装后的结果下次才能验证.下面的这些都是合格的.
	 * (chongszzxt)重生至尊修昙, 重生之诛仙湉, 重生之诛仙绹, 重生之贼心偷, 重生之贼心偸, 重生之追凶褪, 重生之再续炭, 重生之走向陶, 重生之再续蹄, 重生之诛仙缇...
	 * 到用户在输入一个x的时候,采取验证上面的里面是不是合法的,这样浪费很多次验证.树的头要遍历很多次.
	 * (chongszzxtx)重生之贼鉶天序, 重生之贼心天嘻, 重生之贼心天婿, 重生之贼鉶天姓, 重生之贼心天醒, 重生之贼鉶天虚, 重生之贼心天歆, 重生之贼心天歇...
	 * 所以改为每次验证前缀,如果前缀合法,那么取得前缀的node,直接从这个node开始遍历.节省遍历的长度.
	 * Date : 2012-11-22
	 * @param key
	 * @param startNode
	 * @return
	 */
	public boolean contains(String key, TSTNode startNode) {
		if (key == null || startNode == null || key.length() == 0) {
			return false;
		}//一些必要条件的检查

		TSTNode currentNode = startNode.relatives[TSTNode.EQKID];
		int charIndex = 0;
		while (true) {
			if (currentNode == null) {
				return false;
			}
			int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return true;
				}
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	/**
	 * Returns a <code>List</code> of keys that almost match the argument key.
	 * Keys returned will have exactly diff characters that do not match the
	 * target key, where diff is equal to the last value passed in as an
	 * argument to the <code>setMatchAlmostDiff</code> method.
	 * <p>
	 * If the <code>matchAlmost</code> method is called before the
	 * <code>setMatchAlmostDiff</code> method has been called for the first
	 * time, then diff = 0.
	 * 
	 * @param key
	 *            The target key.
	 * @return A <code>List</code> with the results.
	 */
	public List<String> matchAlmost(String key) {
		return matchAlmost(key, defaultNumReturnValues);
	}

	/**
	 * Returns a <code>List</code> of keys that almost match the argument key.
	 * Keys returned will have exactly diff characters that do not match the
	 * target key, where diff is equal to the last value passed in as an
	 * argument to the <code>setMatchAlmostDiff</code> method.
	 * <p>
	 * If the <code>matchAlmost</code> method is called before the
	 * <code>setMatchAlmostDiff</code> method has been called for the first
	 * time, then diff = 0.
	 * 
	 * @param key
	 *            The target key.
	 * @param numReturnValues
	 *            The maximum number of values returned by this method.
	 * @return A <code>List</code> with the results
	 */
	public List<String> matchAlmost(CharSequence key, int numReturnValues) {
		//							当前节点	，一个游标  ，最大模糊	，关键字 ， 返回结果数量										，
		return matchAlmostRecursion(rootNode, 0, matchAlmostDiff, key, ((numReturnValues < 0) ? -1 : numReturnValues), new Vector<String>(), false);
	}

	/**
	 * Recursivelly vists the nodes in order to find the ones that almost match
	 * a given key.
	 * @param currentNode - The current node.
	 * @param charIndex   - The current char.
	 * @param d           - The number of differences so far.
	 * @param matchAlmostNumReturnValues  -  The maximum number of values in the result <code>List</code>.
	 * @param matchAlmostResult2          -  The results so far.
	 * @param upTo
	 *            If true all keys having up to and including matchAlmostDiff
	 *            mismatched letters will be included in the result (including a
	 *            key that is exactly the same as the target string) otherwise
	 *            keys will be included in the result only if they have exactly
	 *            matchAlmostDiff number of mismatched letters.
	 * @param matchAlmostKey              -  The key being searched.
	 * @return A <code>List</code> with the results.
	 */
	private List<String> matchAlmostRecursion(TSTNode currentNode, int charIndex, int d, CharSequence matchAlmostKey, int matchAlmostNumReturnValues,
			List<String> matchAlmostResult2, boolean upTo) {
		//如果一些必要的条件不满足，直接返回一个空的结果。
		if ((currentNode == null) || (matchAlmostNumReturnValues != -1 && matchAlmostResult2.size() >= matchAlmostNumReturnValues) || (d < 0)
				|| (charIndex >= matchAlmostKey.length())) {
			return matchAlmostResult2;
		}
		//char比较，char的unicode差,  arg0>arg1是正数，否则是负数 ，   
		int charComp = compareCharsAlphabetically(matchAlmostKey.charAt(charIndex), currentNode.splitchar);

		List<String> matchAlmostResult = matchAlmostResult2;//一个空的list，实际上是一个 Vector

		if ((d > 0) || (charComp < 0)) { //如果charComp<0 ，说明比当前节点小，就处理左节点
			matchAlmostResult = matchAlmostRecursion(currentNode.relatives[TSTNode.LOKID], charIndex, d, matchAlmostKey, matchAlmostNumReturnValues,
					matchAlmostResult, upTo);
		}

		int nextD = (charComp == 0) ? d : d - 1;
		boolean cond = (upTo) ? (nextD >= 0) : (nextD == 0);

		//如果key的length和游标长度一致，并且。。那么结果集添加这个节点
		if ((matchAlmostKey.length() == charIndex + 1) && cond && (currentNode.data != null)) {
			matchAlmostResult.add(getKey(currentNode));//getKey(currentNode)根据这个node，一直找中间的节点，走到结尾后，用每个splitchar拼接出一个String
		}

		//递归调用
		matchAlmostResult = matchAlmostRecursion(currentNode.relatives[TSTNode.EQKID], charIndex + 1, nextD, matchAlmostKey,
				matchAlmostNumReturnValues, matchAlmostResult, upTo);

		if ((d > 0) || (charComp > 0)) {//如果charComp>0，说明比当前节点值大，处理右节点
			matchAlmostResult = matchAlmostRecursion(currentNode.relatives[TSTNode.HIKID], charIndex, d, matchAlmostKey, matchAlmostNumReturnValues,
					matchAlmostResult, upTo);
		}
		return matchAlmostResult;
	}

	/**
	 * Returns an alphabetical <code>List</code> of all keys in the trie that
	 * begin with a given prefix. Only keys for nodes having non-null data are
	 * included in the <code>List</code>.
	 * 
	 * @param prefix
	 *            Each key returned from this method will begin with the
	 *            characters in prefix.
	 * @return A <code>List</code> with the results.
	 */
	public List<String> matchPrefix(String prefix) {
		return matchPrefix(prefix, defaultNumReturnValues);
	}

	/**
	 * Returns an alphabetical <code>List</code> of all keys in the trie that
	 * begin with a given prefix. Only keys for nodes having non-null data are
	 * included in the <code>List</code>.
	 * 
	 * @param prefix
	 *            Each key returned from this method will begin with the
	 *            characters in prefix.
	 * @param numReturnValues
	 *            The maximum number of values returned from this method.
	 * @return A <code>List</code> with the results
	 */
	public List<String> matchPrefix(CharSequence prefix, int numReturnValues) {
		Vector<String> sortKeysResult = new Vector<String>();
		TSTNode startNode = getNode(prefix);
		if (startNode == null) {
			return sortKeysResult;
		}

		if (startNode.data != null) {
			sortKeysResult.addElement(getKey(startNode));
		}

		return sortKeysRecursion(startNode.relatives[TSTNode.EQKID], ((numReturnValues < 0) ? -1 : numReturnValues), sortKeysResult);
	}

	/**
	 * Returns keys sorted in alphabetical order. This includes the current Node
	 * and all nodes connected to the current Node.
	 * <p>
	 * Sorted keys will be appended to the end of the resulting
	 * <code>List</code>. The result may be empty when this method is invoked,
	 * but may not be <code>null</code>.
	 * 
	 * @param currentNode  The current node.
	 * @param sortKeysNumReturnValues  The maximum number of values in the result.
	 * @param sortKeysResult2  The results so far.
	 * @return A <code>List</code> with the results.
	 */
	private List<String> sortKeysRecursion(TSTNode currentNode, int sortKeysNumReturnValues, List<String> sortKeysResult2) {
		if (currentNode == null) {
			return sortKeysResult2;
		}
		List<String> sortKeysResult = sortKeysRecursion(currentNode.relatives[TSTNode.LOKID], sortKeysNumReturnValues, sortKeysResult2);

		if (sortKeysNumReturnValues != -1 && sortKeysResult.size() >= sortKeysNumReturnValues) {
			return sortKeysResult;
		}

		if (currentNode.data != null) {
			sortKeysResult.add(getKey(currentNode));
		}
		sortKeysResult = sortKeysRecursion(currentNode.relatives[TSTNode.EQKID], sortKeysNumReturnValues, sortKeysResult);

		return sortKeysRecursion(currentNode.relatives[TSTNode.HIKID], sortKeysNumReturnValues, sortKeysResult);
	}

	public List<Hit> matchPrefixHit(String prefix) {
		return matchPrefixHit(prefix, defaultNumReturnValues);
	}

	public List<Hit> matchPrefixHit(CharSequence prefix, int numReturnValues) {
		Vector<Hit> sortKeysResult = new Vector<Hit>();
		TSTNode startNode = getNode(prefix);
		if (startNode == null) {
			return sortKeysResult;
		}

		if (startNode.data != null) {
			sortKeysResult.addElement(new Hit(getKey(startNode), (int) startNode.data));
		}

		return sortKeysRecursionHit(startNode.relatives[TSTNode.EQKID], ((numReturnValues < 0) ? -1 : numReturnValues), sortKeysResult);
	}

	private List<Hit> sortKeysRecursionHit(TSTNode currentNode, int sortKeysNumReturnValues, List<Hit> sortKeysResult2) {
		if (currentNode == null) {
			return sortKeysResult2;
		}
		List<Hit> sortKeysResult = sortKeysRecursionHit(currentNode.relatives[TSTNode.LOKID], sortKeysNumReturnValues, sortKeysResult2);

		if (sortKeysNumReturnValues != -1 && sortKeysResult.size() >= sortKeysNumReturnValues) {
			return sortKeysResult;
		}

		if (currentNode.data != null) {
			sortKeysResult.add(new Hit(getKey(currentNode), (int) currentNode.data));
		}
		sortKeysResult = sortKeysRecursionHit(currentNode.relatives[TSTNode.EQKID], sortKeysNumReturnValues, sortKeysResult);

		return sortKeysRecursionHit(currentNode.relatives[TSTNode.HIKID], sortKeysNumReturnValues, sortKeysResult);
	}

	/**
	 * Returns the number of nodes in the trie that have non-null data.
	 * 
	 * @return The number of nodes in the trie that have non-null data.
	 */
	public int numDataNodes() {
		return numDataNodes(rootNode);
	}

	/**
	 * Returns the number of nodes in the subtrie below and including the
	 * starting node. The method counts only nodes that have non-null data.
	 * 
	 * @param startingNode
	 *            The top node of the subtrie. the node that defines the
	 *            subtrie.
	 * @return The total number of nodes in the subtrie.
	 */
	protected int numDataNodes(TSTNode startingNode) {
		return recursiveNodeCalculator(startingNode, true, 0);
	}

	/**
	 * Returns the total number of nodes in the trie. The method counts nodes
	 * whether or not they have data.
	 * 
	 * @return The total number of nodes in the trie.
	 */
	public int numNodes() {
		return numNodes(rootNode);
	}

	/**
	 * Returns the total number of nodes in the subtrie below and including the
	 * starting Node. The method counts nodes whether or not they have data.
	 * 
	 * @param startingNode
	 *            The top node of the subtrie. The node that defines the
	 *            subtrie.
	 * @return The total number of nodes in the subtrie.
	 */
	protected int numNodes(TSTNode startingNode) {
		return recursiveNodeCalculator(startingNode, false, 0);
	}

	/**
	 * Recursivelly visists each node to calculate the number of nodes.
	 * 
	 * @param currentNode
	 *            The current node.
	 * @param checkData
	 *            If true we check the data to be different of <code>null</code>
	 *            .
	 * @param numNodes2
	 *            The number of nodes so far.
	 * @return The number of nodes accounted.
	 */
	private int recursiveNodeCalculator(TSTNode currentNode, boolean checkData, int numNodes2) {
		if (currentNode == null) {
			return numNodes2;
		}
		int numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.LOKID], checkData, numNodes2);

		numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.EQKID], checkData, numNodes);

		numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.HIKID], checkData, numNodes);
		if (checkData) {
			if (currentNode.data != null) {
				numNodes++;
			}
		} else {
			numNodes++;
		}
		return numNodes;
	}

	/**
	 * Sets the number of characters by which words can differ from target word
	 * when calling the <code>matchAlmost</code> method.
	 * <p>
	 * Arguments less than 0 will set the char difference to 0, and arguments
	 * greater than 3 will set the char difference to 3.
	 * @param diff
	 *            The number of characters by which words can differ from target
	 *            word.
	 */
	public void setMatchAlmostDiff(int diff) {
		if (diff < 0) {
			matchAlmostDiff = 0;
		} else if (diff > 3) {
			matchAlmostDiff = 3;
		} else {
			matchAlmostDiff = diff;
		}
	}

	/**
	 * Sets the default maximum number of values returned from the
	 * <code>matchPrefix</code> and <code>matchAlmost</code> methods.
	 * <p>
	 * The value should be set this to -1 to get an unlimited number of return
	 * values. note that the methods mentioned above provide overloaded versions
	 * that allow you to specify the maximum number of return values, in which
	 * case this value is temporarily overridden.
	 ** @param num
	 *            The number of values that will be returned when calling the
	 *            methods above.
	 */
	public void setNumReturnValues(int num) {
		defaultNumReturnValues = (num < 0) ? -1 : num;
	}

	/**
	 * Returns keys sorted in alphabetical order. This includes the start Node
	 * and all nodes connected to the start Node.
	 * <p>
	 * The number of keys returned is limited to numReturnValues. To get a list
	 * that isn't limited in size, set numReturnValues to -1.
	 * 
	 * @param startNode   The top node defining the subtrie to be searched.
	 * @param numReturnValues  The maximum number of values returned from this method.
	 * @return A <code>List</code> with the results.
	 */
	protected List<String> sortKeys(TSTNode startNode, int numReturnValues) {
		return sortKeysRecursion(startNode, ((numReturnValues < 0) ? -1 : numReturnValues), new Vector<String>());
	}

	/** An inner class of Ternary Search Trie that represents a node in the trie. */
	public static final class TSTNode {
		public final static int PARENT = 0, LOKID = 1, EQKID = 2, HIKID = 3;//定义的常量，用常量名代替位置。
		public Object data;//The key to the node.
		public TSTNode[] relatives = new TSTNode[4];//数组存储父节点、坐节点、中央节点、右节点
		public char splitchar;//字符串分割后的一个char，当前节点的char

		/** 构造方法，parent直接赋值给第一个数组
		 * @param splitchar The char used in the split.
		 * @param parent The parent node.  */
		protected TSTNode(char splitchar, TSTNode parent) {
			this.splitchar = splitchar;
			relatives[PARENT] = parent;
		}
	}
}
